Thread Scheduling

Depending on the current environment, an RTSS or Proxy thread state might be waiting (i.e. for an event, resource, or amount of time), ready-to-run, or running. The scheduler uses priority levels to determine which ready-to-run thread will be allowed to run next. Each RTSS processor has its own ready queue.

Priority Levels

The RTSS environment provides thread priority levels RT_PRIORITY_MIN (0) though RT_PRIORITY_MAX (127). An RTSS thread's priority level can be set using RtSetThreadPriority where the priority can be any integer from RT_PRIORITY_MIN to RT_PRIORITY_MAX. A Proxy thread's priority level can be set using RtSetProxyThreadPriority or RtkSetProxyThreadPriority where the priority can be any integer from RT_PRIORITY_MIN to RT_PRIORITY_MAX.

Example Application Environment

To illustrate how threads move in and out of the run state on a single processor, an application with three threads will be used. This example application environment includes:

• Thread Th1, performing a critical task, at high priority level 60
• Thread Th2, performing an important task, at medium priority level 40
• Thread Th3, performing a maintenance task at low priority level 20

In a simple environment, with no shared resources, any time that the highest priority thread Th1 is ready-to-run, it will be allowed to execute. When thread Th1 has completed its task, the next highest priority ready-to-run thread will be allowed to execute.

For an example, see SMP Sample.

Priority Inversion

Example 1: All threads are scheduled to run on the same core

In a shared resource environment, two or more threads, such as Th1 and Th3, may need to share a single resource, whose access is controlled by mutex M1. In cases where a low priority thread has ownership of the shared resource that a high priority thread needs, the high priority thread will be blocked until the low priority thread has released the resource. This is called priority inversion since the relative priorities of the threads are effectively inverted.

The execution delay experienced by a critical thread in a priority inversion situation can be exacerbated if some other medium priority thread, which does not depend on the shared resource, takes precedence over the low priority thread if run on the same processor. Until the low priority thread is allowed to run, the shared resource will not be released.

In the scenario below, all threads are scheduled to run on the same core:

1. A maintenance (low priority 20) thread Th3 is ready-to-run and given control of the CPU. Thread Th3 begins by waiting for, and then acquiring ownership of, mutex M1.
2. An important (medium priority 30) thread Th2 becomes ready-to-run. Thread Th3 is returned to a ready-to-run state and thread Th2 begins to run.
3. A critical (high priority 60) thread Th1 becomes ready-to-run. Thread Th2 is returned to a ready-to-run state and thread Th1 begins to run.
4. Thread Th1 requests ownership of mutex M1 (by calling either RtWaitForSingleObject or RtWaitForSingleObject(Ex), or RtWaitForMultipleObjects or RtWaitForMultipleObjects(Ex)).
5. Since mutex M1 is currently owned by thread Th3, and not available, thread Th1 enters a wait state
6. The highest priority ready-to-run thread (which is now Th2) is started and runs until completion.
7. Thread Th3 is then moved from a ready-to-run state, completes its use of the resource, and releases mutex M1.
8. Thread Th1 acquires mutex M1 and runs until completion.
9. When no higher priority threads are ready-to-run, thread Th3 is allowed to run again.

Example 2: Threads are scheduled to run on multiple cores:

1. A maintenance (low priority 20) thread Th3 is ready-to-run and given control of an RTSS Processor P1. Thread Th3 begins by waiting for, and then acquiring ownership of, mutex M1.
2. An important (medium priority 30) thread Th2 becomes ready-to-run on RTSS processor P1. Thread Th3 is returned to a ready-to-run state and thread Th2 begins to run.
3. A critical (high priority 60) thread Th1 becomes ready-to-run on RTSS processor P2, and begins to run.
4. Thread Th1 requests ownership of mutex M1 (by calling either RtWaitForSingleObject or RtWaitForMultipleObjects).
5. Since mutex M1 is currently owned by thread Th3, and not available, thread Th1 enters a wait state.
6. Th2 on RTSS processor P1 runs until completion.
7. Thread Th3 is then moved from a ready-to-run state on RTSS processor P1, completes its use of the resource, and releases mutex M1.
8. Thread Th1 acquires mutex M1 and runs until completion on RTSS processor P2.

Priority Inversion Protocols

Even when developers carefully manage the use of shared resources, there may still be situations where priority inversion can arise and impact application behavior. Because of this, the RTX64 scheduler provides:

• Priority Promotion with Tiered Demotion - Elevates a low priority thread to the level of the highest priority thread that is waiting for a mutex. When the promoted thread has released the mutex requested by a higher priority thread, it is demoted, allowing the higher priority blocked thread to acquire the mutex and to run.
• Disable - Does not elevate priorities in cases where a higher priority thread is waiting on a mutex held by a lower priority thread.

NOTE: This setting can be configured through the RTX64 Control Panel on the Change Internal System Behavior page.

Priority Promotion with Tiered Demotion

When RTX64 priority promotion with tiered demotion is implemented, a lower-priority thread that owns a mutex needed by a higher priority thread will have its priority temporarily promoted to that of the high priority waiting thread until it has released the requested mutex.

This tiered implementation uses an internal mutex priority to keep track of priority promotion causing mutexes. On each call to RtReleaseMutex the thread’s priority will be checked to see if its priority can be demoted based on the internal priorities of the remaining mutexes held. This tiered demotion allows promoted priorities to be demoted as soon as possible, promoting threads only as high as necessary based on higher priority waiting threads.

Priority promotion with tiered demotion in a scenario where two different priority threads share a resource controlled by a mutex set to run on the same processor is illustrated as follows:

1. A maintenance (low priority 20) thread Th3 is ready-to-run and given control of the CPU.Thread Th3 begins by waiting for, and then acquiring ownership of, mutex M1.
2. An important (medium priority 30) thread Th2 becomes ready-to-run. Thread Th3 is returned to a ready-to-run state and thread Th2 begins to run.
3. A critical (high priority 60) thread Th1 becomes ready-to-run. Thread Th2 is returned to a ready-to-run state and thread Th1 begins to run.
4. Th1 performs some work and then requests ownership of mutex M1.
5. When thread Th1 requests mutex M1 with a call to either RtWaitForSingleObject or RtWaitForSingleObject(Ex), or RtWaitForMultipleObjects or RtWaitForMultipleObjects(Ex), the owner of mutex M1 (which is thread Th3) is promoted to the priority of the requesting thread (priority 60).
6. Thread Th3, now ready-to-run at priority 60, runs until it has finished using the shared resource and releases mutex M1. After calling RtReleaseMutex, thread Th3 returns to its native priority (priority 20).
7. Thread Th1 acquires mutex M1 and, as the highest priority ready-to-run thread, is able to run to completion.

Priority promotion with tiered demotion in a scenario where two different priority threads share a resource controlled by a mutex set to run different RTSS processors is illustrated as follows:

1. A maintenance (low priority 20) thread Th3 is ready-to-run and given control of an RTSS processor P1. Thread Th3 begins by waiting for, and then acquiring ownership of, mutex M1.
2. An important (medium priority 30) thread Th2 becomes ready-to-run on RTSS processor P1. Thread Th3 is returned to a ready-to-run state and thread Th2 begins to run.
3. A critical (high priority 60) thread Th1 becomes ready-to-run on RTSS processor P2 and begins to run.
4. Thread Th1 requests ownership of mutex M1 (by calling either RtWaitForSingleObject or RtWaitForMultipleObjects).
5. Since mutex M1 is currently owned by thread Th3, and is not available, thread Th3 is promoted to the priority of the requesting thread (priority 60) and, thread Th1 enters a wait state.
6. Since Thread 3 is now a higher priority than thread Th2, thread Th3 is returned to a ready-to-run state and thread Th3 begins to run on RTSS Processor P1.
7. Thread Th3 completes its use of the resource, and releases mutex M1 and returns to its native priority (priority 20).
8. Thread Th1 acquires mutex M1 and runs until completion on RTSS processor P2.
9. Since thread Th3 is now less than thread Th2, thread Th2 becomes ready-to-run on RTSS processor P1. Thread Th3 is returned to a ready-to-run state and thread Th2 begins to run until completion.
10. Then if Th3 is not finished it will run until completed.

Priority promotion with tiered demotion in a scenario where a low priority thread has ownership of a single mutex that is needed by two higher priority threads on the same RTSS processor, is illustrated as follows:

1. A maintenance (low priority 20) thread Th3 is ready-to-run and given control of the CPU.Thread Th3 begins by waiting for (RtWaitForSingleObject) and then acquiring ownership of mutex M1.
2. An important (medium priority 30) thread Th2 becomes ready-to-run, preempts thread Th3 and calls RtWaitForSingleObject or RtWaitForMultipleObjects, requesting ownership of mutex M1. Since the mutex is unavailable, thread Th2 goes into a wait state.
3. As a result of Thread Th2's call to RtWaitForSingleObject or RtWaitForMultipleObjects, thread Th3 is promoted to the priority (30) of thread Th2.
4. A critical (high priority 20) thread Th1 becomes ready-to-run, preempts thread Th3 and calls RtWaitForSingleObject or RtWaitForMultipleObjects, requesting ownership of mutex M1. Since the mutex is unavailable, thread Th1 goes into a wait state
5. As a result of Thread Th1's call to RtWaitForSingleObject or RtWaitForMultipleObjects, thread Th3 is promoted to the priority (60) of thread Th1.
6. Thread Th3 completes its use of the shared resource and releases ownership of mutex M1. As a result of its call to RtReleaseMutex, thread Th3 is demoted back to its native priority (20).
7. Thread Th1 runs until completion (releasing mutex M1).
8. Thread Th2 runs until completion (releasing mutex M1).
9. Thread Th3 runs until completion.

Priority Inversion Protocol - Disable

When priority promotion is disabled, the Subsystem does not do anything to track thread priority in relation to shared resources. This can be useful when developers want total control of thread priority. If detailed attention is given to the management and use of each shared resource, an application developer should not require priority inversion prevention.  However, when not activating a priority inversion protocol, developers should take extra care with their application implementation, as priority inversion can still occur.

The graphic below shows a scenario where all threads are scheduled to run on the same core:

1. A maintenance (low priority 20) thread Th3 is ready-to-run and given control of the CPU. Thread Th3 begins by waiting for, and then acquiring ownership of, mutex M1.
2. An important (medium priority 30) thread Th2 becomes ready-to-run. Thread Th3 is returned to a ready-to-run state and thread Th2 begins to run.
3. A critical (high priority 60) thread Th1 becomes ready-to-run. Thread Th2 is returned to a ready-to-run state and thread Th1 begins to run.
4. Thread Th1 requests ownership of mutex M1 (by calling either RtWaitForSingleObject or RtWaitForMultipleObjects).
5. Since mutex M1 is currently owned by thread Th3, and not available, thread Th1 enters a wait state
6. The highest priority ready-to-run thread (which is now Th2) is started and runs until completion.
7. Thread Th3 is then moved from a ready-to-run state, completes its use of the resource, and releases mutex M1.
8. Thread Th1 acquires mutex M1 and runs until completion.
9. When no higher priority threads are ready-to-run, thread Th3 is allowed to run again.

Scenario where threads are scheduled to run on multiple cores is illustrated as follows:

1. A maintenance (low priority 20) thread Th3 is ready-to-run and given control of an RTSS processor P1. Thread Th3 begins by waiting for, and then acquiring ownership of, mutex M1.
2. An important (medium priority 30) thread Th2 becomes ready-to-run on RTSS processor P1. Thread Th3 is returned to a ready-to-run state and thread Th2 begins to run.
3. A critical (high priority 60) thread Th1 becomes ready-to-run on RTSS processor P2, and begins to run.
4. Thread Th1 requests ownership of mutex M1 (by calling either RtWaitForSingleObject or RtWaitForMultipleObjects).
5. Since mutex M1 is currently owned by thread Th3, and not available, thread Th1 enters a wait state.
6. Th2 on RTSS processor P1 runs until completion.
7. Thread Th3 is then moved from a ready-to-run state on RTSS processor P1, completes its use of the resource, and releases mutex M1.
8. Thread Th1 acquires mutex M1 and runs until completion on RTSS processor P2.